// 原整数数组 nums 按升序排列，数组中的值 互不相同 。
// 给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，
// 则返回它的下标，否则返回 -1 。

// 输入：nums = [4,5,6,7,0,1,2], target = 0
// 输出：4


// 无法知道数组是如何旋转的, 但原数组是有序的, 
// 假设原旋转点为x+1, 则nums[x+1] - nums[len - 1]和另一部分nums[0] - nums[x]是有序的
// 旋转后左半部分大于右半部分, 根据target和nums[0]的比较可以知道目标在哪一半
// 再判断mid在哪一半, 我们可以缩小范围, 逐渐逼近target
int search(int* nums, int numsSize, int target){
    int left = 0, right = numsSize - 1;

    while (left <= right) {
        int mid = left + (right - left)/2;
        if (nums[mid] == target) return mid;

        if (target >= nums[0]) {    // 目标在左半部分
            
            if (nums[mid] >= nums[0]) { // mid也在左半部分nums[0, x], 进入正常的二分查找
                if (nums[mid] < target) left = mid + 1; 
                else right = mid - 1;   
            } 
            else {    // mid在右半部分, 而target在左边
                right = mid - 1;    // 直接向左边逼近
            }

        } else {    // 目标在右半部分nums[x+1, len-1]
            
            if (nums[mid] >= nums[0]) {   // mid在左边, 而target在右边
                left = mid + 1;    // 直接向右边逼近
            }
            else {    // mid也在右半边nums[x+1, len-1], 进入正常的二分查找
                if (nums[mid] < target) left = mid + 1; // target在nums[mid, len-1]
                else right = mid - 1;   // target在nums[x+1, mid]
            }
        }
    }
    return -1;
}